f 8 and f 9 are standardized by 3GPP to provide confidentiality and integrity, respectively. It was claimed that f 8 and f 9 are secure if the underlying block cipher is a PseudoRandom Permutation (PRP), where f 9 is a slightly modified version of f 9. In this paper, however, we disprove both claims by showing a counterexample. We first construct a PRP F with the following property: There is a non-zero constant Cst such that for any key K, FK()=(). We then show that f 8 and f 9 are completely insecure if F is used as the underlying block cipher. Therefore, PRP assumption does not necessarily imply the security of f 8 and f 9, and it is impossible to prove their security under PRP assumption. It should be stressed that these results do not imply the original f 8 and f 9 (with KASUMI as the underlying block cipher) are insecure, or broken. They simply undermine their provable security.

It is known that a super-pseudorandom permutation can be constructed from a pseudorandom function f and two universal hash functions, h and h′. It is a four round Feistel permutation denoted by φ(hk,f,f,h′k′). In this paper, we show how to re-use the secret key for f in this construction. Specifically, we show that (1) the same key can be used for both h and h′, and (2) the key for h and h′can be derived from f. As a result, our construction requires only the key for f as a secret key, and it preserves computational efficiency and security. We show the full security proof of our construction. Also, we derive a similar result for a five round MISTY-type permutation.

In the key recovery variant of the interpolation attack, exhaustive search is required to find the last round key Km. Therefore, this attack is almost impractical if the size of Km is too large. In this paper, we show that Km can be very efficiently obtained if F(K,x) can be approximated by a low degree polynomial gx(K) in K for any fixed x, where F is a round function of Feistel type block ciphers.

This paper discusses the problem of reducing the number of keys required to authenticate a source state (plaintext), as well as introducing a new way of constructing authentication codes. The construction uses association schemes, which are well-defined schemes in combinatorial design theory. The association scheme on the message (ciphertext) space is established by defining two relations between any two messages: The 1st relation is when the two messages do not share a common key, and the 2nd relation is when they do. Using association schemes of the triangular and group divisible types, we are able to reduce the number of keys.

In a (k,n) threshold digital signature scheme, k out of n signers must cooperate to issue a signature. In this paper, we show an efncient (k,n) threshold EIGamal type digital signature scheme with no trusted center. We first present a variant of EIGamal type digital signature scheme which requires only a linear combination of two shared secrets when applied to the (k,n)-threshold scenario. More precisely, it is a variant of Digital Signature Standard (DSS) which was recommended by the U.S. National Institute ofStandard and Technology (NIST). We consider that it is meaningful to develop an efficient (k,n)-threshold digital signature scheme for DSS. The proposed (k,n)-threshold digital signature scheme is proved to be as secure as the proposed variant of DSS against chosen message attack.

This paper presents a combinatiorial characterization of broadcast authentication in which a transmitter broadcasts v messages e1(s), , ev(s) to authenticate a source state s to all n receivers so that any k receivers cannot cheat any other receivers, where ei is a key. Suppose that each receiver has l keys. First, we prove that k < l if v < n. Then we show an upper bound of n such that n v(v - 1)/l(l - 1) for k = l - 1 and n /+ for k < l - 1. Further, a scheme for k = 1 - 1 which meets the upper bound is presented by using a BIBD and a scheme for k < l - 1 such than n = / is presented by using a Steiner system. Some other efficient schemes are also presented.

This paper presents a reshufflable and laziness tolerant mental card game protocol. First, our protocol can reshuffle any subset of cards. For example, some opened cards and some face down cards can be shuffled together. Next, we consider two types of honest players, currently active and currently nonactive. A player is currently nonactive if he dropped out the game or he declared "pass" and has not declared "rejoin" yet. In the proposed protocol, if more than half of the players are currently active, they can play the game. In this case, the privacy of the currently nonactive players are kept secret.

Lower bounds on the size of shares |Vi| which are more tight than |Vi>| |S| is the size of the secret, are known only for some graphical access structures. This paper shows lower bounds on |Vi| greater than |S| for some non-graphical access structures Γ. We first prove that if {P1, Pi} Γ-for any Pi P^ = {P2, , Pn} and Γ ^= 2P^ Γ is the access structure of a (k, n-1) -threshold scheme on P^, thenmaxilog|Vi>| n+k-3/n-1 log|S|for Pi {P1, P2, , Pn}. Next, we show that maxilog |Vi| 1.5log |S| holds for a wider class of access structures.

For RSA, May showed a deterministic polynomial time equivalence of computing d to factoring N(=pq). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where N=prq while ed=1 mod(p-1)(q-1). In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix T to which LLL algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.

In this paper, we introduce the intermediate hashed Diffie-Hellman (IHDH) assumption which is weaker than the hashed DH (HDH) assumption (and thus the decisional DH assumption), and is stronger than the computational DH assumption. We then present two public key encryption schemes with short ciphertexts which are both chosen-ciphertext secure under this assumption. The short-message scheme has smaller size of ciphertexts than Kurosawa-Desmedt (KD) scheme, and the long-message scheme is a KD-size scheme (with arbitrary plaintext length) which is based on a weaker assumption than the HDH assumption.

This paper shows a simple methodology for shortening a ciphertext of reproducible key encapsulation mechanisms. Specifically, it transforms a key encapsulation mechanism having OW-CCCA security and reproducibility into that of IND-CCA secure in the random oracle model whose ciphertext is shorter. Various existing chosen-ciphertext secure key encapsulation mechanisms (in the standard model) are reproducible, and thus their ciphertext can be shortened by the proposed transformation. The transformed scheme requires only one additional hashing for encryption. This property enables us to implement both the original scheme and the transformed scheme into a single chip simultaneously with small gate-size overhead. Using this chip, a sender can flexibly switch schemes to encrypt a message in a message-by-message manner. Such a use of schemes is also analyzed.

This paper presents an efficient ZKIP for SAT by using the K-th reisude cryptosystem. The proposed ZKIP is generalized to a ZKIP for the following problem. Let Fi(i=1, 2, , m) be a rational function over mod K. Given {Fi}, does there exist (x1, x2, , xn) such that Fi(x1, x2, , xn)=0 mod K for i=1, 2, , m?

Verifiable random functions (VRF), proposed in 1999, and selectively convertible undeniable signature (SCUS) schemes, proposed in 1990, are apparently thought as independent primitives in the literature. In this paper, we show that they are tightly related in the following sense: VRF is exactly SCUS; and the reverse also holds true under a condition. This directly yields several deterministic SCUS schemes based on existing VRF constructions. In addition, we create a new probabilistic SCUS scheme, which is very compact. We build efficient confirmation and disavowal protocols for the proposed SCUS schemes, based on what we call zero-knowledge protocols for generalized DDH and non-DDH. These zero-knowledge protocols are built either sequential, concurrent, or universally composable.

A compromising technique is proposed for deterring clients from cheating by robot players in skill-based real-time network games. This technique is to inject a fair random noise into the manual input for a real-time game modeled as a chaotic dynamical system. The fair random noise is determined by means of the bit commitment protocol so that neither host nor client can control the noise in their favor. A scenario possibly plotted by a robot player for its victory may be spoiled by slight noise injection because of the sensitivity of chaotic systems to the input. The noise injection brings a luck-based factor into a skill-based game. In this sense, the technique proposed in this paper is not a solution but a compromise for the inherent problem of robot players with the skill-based network games. An example implementation of pinball is presented.

In this paper, we study multi-collision probability. For a hash function H :D R with |R|=n, it has been believed that we can find an s-collision by hashing Q=n(s-1)/s times. We first show that this probability is at most 1/s! for any s, which is very small for large s (for example, s=n(s-1)/s). Thus the above folklore is wrong for large s. We next show that if s is small, so that we can assume Q-s ≈ Q, then this probability is at least 1/s!-1/2(s!)2, which is very high for small s (for example, s is a constant). Thus the above folklore is true for small s. Moreover, we show that by hashing (s!)1/sQ+s-1 (≤ n) times, an s-collision is found with probability approximately 0.5 for any n and s such that (s!/n)1/s ≈ 0. Note that if s=2, it coincides with the usual birthday paradox. Hence it is a generalization of the birthday paradox to multi-collisions.

This paper shows a general method how to construct a public key cryptosystem based on the γ-th residue problem. The necessary and sufficient conditions are presented which the parameters must satisfy for any γ (both for odd and even). The proposed cryptosystem has many applications, an efficient mental poker protocol, for example (Note that the number of cards is 52, which is even).

We present and analyze an adaptive chosen ciphertext secure (IND-CCA) identity-based encryption scheme (IBE) based on the well studied Decisional Diffie-Hellman (DDH) assumption. The scheme is provably secure in the standard model assuming the adversary can corrupt up to a maximum of k users adaptively. This is contrary to the Boneh-Franklin scheme which holds in the random-oracle model.

Mobile communication networks need public key cryptosystems that offer both low computation cost and user authentication. Tatebayashi et al. showed a key distribution protocol for such networks at Crypto'89 based on low exponent RSA. This paper shows that their protocol is not secure. We also present two types of secure and efficient key distribution protocols.

In this paper, we propose a new leakage-resilient identity-based encryption (IBE) scheme that is secure against chosen-ciphertext attacks (CCA) in the bounded memory leakage model. The security of our scheme is based on the external k-Linear assumption. It is the first CCA-secure leakage-resilient IBE scheme which does not depend on q-type assumptions. The leakage rate 1/10 is achieved under the XDLIN assumption (k=2).

This paper points out that there are two types of claw free families with respect to a level of claw freeness. We formulate them as weak claw free families and strong claw free families. Then, we present sufficient conditions for each type of claw free families. (A similar result is known for weak claw free families.) They are represented as some algebraic forms of one way functions. A new example of strong claw free families is also given.